__author__ = 'st316'
'''
Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

two list: a less a great then link two list
'''


# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

    def toString(self):
        cur = self
        s = ''
        while cur.next:
            s += str(cur.val) + ' -> '
            cur = cur.next
        return s + str(cur.val)


class Solution:
    # @param head, a ListNode
    # @param x, an integer
    # @return a ListNode
    def partition(self, head, x):
        if not head or not head.next:
            return head
        h1 = h2 = None
        p1 = p2 = None
        p = head
        while p:
            q = p.next
            p.next = None
            if p.val < x:
                if not h1:
                    h1 = p1 = p
                else:
                    p1.next = p
                    p1 = p
            else:
                if not h2:
                    h2 = p2 = p
                else:
                    p2.next = p
                    p2 = p
            p = q
        if h1:
            p1.next = h2
        return h1 if h1 else h2


if __name__ == '__main__':
    s = Solution()
    l = [1, 1]
    ll = ListNode(l[0])
    cur = ll
    for v in l[1:]:
        cur.next = ListNode(v)
        cur = cur.next
    print s.partition(ll, 0).toString()